//
//  This computes the numbers of solid partitions of integers <=N using an
//  algorithm due to Knuth.
//  Created by B. Srivatsan around August/September 2010.
//  Copyright (c) 2010 srivatsan1991@gmail.com All rights reserved.
//
#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii, int> piii;

const int MAX = 1000;

// a[i] = number of 1-d partitions of sum i //
ll a[MAX+1];
void calculate_1d(int n) {
  for(int i=0; i<=n; i++) a[i]=1;
  for(int k=2; k<=n; k++)
    for(int i=k; i<=n; i++)
      a[i] += a[i-k];
}

// bgf[i] = 2d partitions of sum i calculated using generating function //
ll bgf[MAX+1];
void calculate_2d(int n) {
  for(int i=0; i<=n; i++) bgf[i] = 1;
  for(int k=2; k<=n; k++) for(int p=1; p<=k; p++) 
    for(int i=k; i<=n; i++)
      bgf[i] += bgf[i-k];
}

// cgf[i] = macmahon's conjecture for 3d partitions
ll cgf[MAX+1];
void calculate_3d_macmahon(int n) {
  for(int i=0; i<=n; i++) cgf[i] = 1;
  for(int k=2; k<=n; k++) for(int p=1; p<=((k*(k+1))/2); p++) 
    for(int i=k; i<=n; i++)
      cgf[i] += cgf[i-k];
}

/************** GENERATING TOPOLOGICAL SEQUENCES *****************/
ll d[MAX+1];		// d[i] = no of topological sequences of index i
int cc[MAX+1][MAX+1];	// no. of columns in given plane,row
int pp, n;		// no. of planes and n
piii x[MAX+1]; int k;	// the sequence of positions and its depth
int curidx;

bool possible(int x, int y, int z) {
  if(x>1 && cc[x-1][y] < z) return 0;
  if(y>1 && cc[x][y-1] < z) return 0;
  return 1;
}

void include(int p, int y, int z) {
  k++;
  cc[p][y] = z;
  x[k] = make_pair(pii(p,y), z);
  if(x[k-1] > x[k]) curidx += (k-1);
}
void exclude(int p, int y, int z) {
  if(x[k-1] > x[k]) curidx -= (k-1);
  cc[p][y]--;
  k--;
}

void printconfig() { for(int i=1; i<=k; i++) printf("(%d,%d,%d)  ", x[i].first.first, x[i].first.second, x[i].second); printf("%d\n", curidx+k); }

// count the current config and make ur next move
void gen() {
  if(curidx + k > n) return;
  //printconfig();
  if(x[k].first!=pii(1,1)) d[curidx+k]++;
  int p, r, c, t;
  for(p=1; p<=n; p++) {
    for(r=1; r<=n; r++) {
      c = cc[p][r]+1;
      if(possible(p, r, c)) {
				include(p, r, c);
				gen();
				exclude(p, r, c);
      }
      if(cc[p][r] == 0) break;
    }
    if(cc[p][1] == 0) break;
  }
}

void generate_topological_sequences(int nn) {
  memset(cc, 0, sizeof(cc));
  memset(d, 0, sizeof(d));
    d[0] = 1;
    k=1; x[1] = make_pair(pii(1,1),1);
  cc[1][1] = 1;
  curidx = 0;
  n = nn;
  gen();
    /*
    memset(cc, 0, sizeof(cc));  cc[1][2] = 1;cc[1][1] = 1;
    k=2; x[1] = make_pair(pii(1,1),1);x[2]=make_pair(pii(1,2),1);
    curidx = 0;
    //n = nn;
    gen();

    memset(cc, 0, sizeof(cc));  cc[2][1] = 1;cc[1][1] = 1;
    k=2; x[1] = make_pair(pii(1,1),1);x[2]=make_pair(pii(2,1),1);
    curidx = 0;
    //n = nn;
    gen();
*/
}
//////////////////////////////////////////////

// assumes generate_topological_sequences() and calculate_1d() have been called
ll c[MAX+1];
void calculate_3d_correct(int n) {
  memset(c, 0, sizeof(c));
  for(int i=1; i<=n; i++) {
    for(int j=0; j<=i; j++) c[i] += (a[j]*d[i-j]);
  }
}

int main() {
  //printf("Enter N: ");
  int N=27; //scanf("%d", &N);
  generate_topological_sequences(N);
  calculate_1d(N);
  calculate_3d_correct(N);
  //printf("d[i] = no. of topological sequences of index i\n");
  for(int i=0; i<=N; i++) printf("d[%d] = %lld\n", i, d[i]);
  //printf("c[i] = no. of 3d partitions of i\n");
  //for(int i=1; i<=N; i++) printf("c[%d] = %lld\n", i, c[i]);
}
